Neural Information Processing Systems http://nips.cc/

First provide a summary of the paper, and then address the following criteria: Quality, clarity, originality and significance. Augmentative Message Passing for Traveling Salesman Problem and Graph Partitioning The paper develops messaging passing techniques to approximate two NP-hard problems: TSP and graph partitioning. Using specifics of each problem a graphical model is constructed such that the MAP state gives the solution for the original problem (e.g. using Held-Karp necessary and sufficient conditions for valid tours for the TSP). The resulting model has a very large number of clusters making message passing on the full graph (full set of constraints) infeasible for large problems (even when loops are ignored in the problem and no junction tree is constructed). The paper proposes methods to approximate this by starting with a smaller set of constraints and iteratively adding some. Quality The methods proposed do not come with any guarantee.

The cutting plane method is an augmentative constrained optimization procedure that is often used with continuous-domain optimization techniques such as linear and convex programs. We investigate the viability of a similar idea within message passing -- for integral solutions -- in the context of two combinatorial problems: 1) For Traveling Salesman Problem (TSP), we propose a factor-graph based on Held-Karp formulation, with an exponential number of constraint factors, each of which has an exponential but sparse tabular form.

The cutting plane method is an augmentative constrained optimization procedure that is often used with continuous-domain optimization techniques such as linear and convex programs. We investigate the viability of a similar idea within message passing -- for integral solutions -- in the context of two combinatorial problems: 1) For Traveling Salesman Problem (TSP), we propose a factor-graph based on Held-Karp formulation, with an exponential number of constraint factors, each of which has an exponential but sparse tabular form. In both cases we are able to derive surprisingly simple message updates that lead to competitive solutions on benchmark instances. In particular for TSP we are able to find near-optimal solutions in the time that empirically grows with $N 3$, demonstrating that augmentation is practical and efficient. Papers published at the Neural Information Processing Systems Conference.